﻿/*
* File: construct subgroup function2
* Author: Dongcheng Li
* Date: 20191014
* Purpose: construct subgroup of Zp*
* https://w.ketangpai.com/pages/homework/homework-detail.html
*/
#include <iostream>
#include<stack>
#include<algorithm>
using namespace std;
/*
*Input: an integer p
* Output : return the result of subgroup.
* Purpose : construct subgroup of Zp*
* Method : By using the Fermat’s Little Theorem.
*/
void construct_Subgroup2(int p) {
	int g;
	int order;
	int* a = new int[p];
	int Elements_in_a_Subgroup;
	int n = 0;
	int first_Elements_in_a_Subgroup;
	for (g = 1; g < p; g++)
	{
		Elements_in_a_Subgroup = (g * g) % p;
		a[g - 1] = Elements_in_a_Subgroup;
	}
	sort(a, a + p);
	order = unique(a, a + p) - a;//Must be used after sorting,The return value is the length after deduplication
	cout << "order:" << order;
}
int main()
{
	int prime_P;
	cout << "P:" << endl;
	cin >> prime_P;
	construct_Subgroup2(prime_P);
}